package hard.合并K个升序链表;


/**
 * 合并K个升序链表
 *
 * @author codex
 * @since 2021-09-27
 */
public class MergeKLists {
    
    public ListNode mergeKLists(ListNode[] lists) {
        
        return merge(lists, 0, lists.length - 1);
    }
    
    public ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        
        if (start > end) {
            return null;
        }
        
        int mid = (start + end) / 2;
        
        return mergeTwoListNode(merge(lists, start, mid), merge(lists, mid + 1, end));
    }
    
    public ListNode mergeTwoListNode(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        
        if (l2 == null) {
            return l1;
        }
        
        if (l1.val < l2.val) {
            l1.next = mergeTwoListNode(l1.next, l2);
            return l1;
        }
        
        l2.next = mergeTwoListNode(l1, l2.next);
        return l2;
    }
    
    public static void main(String[] args) {
        MergeKLists m = new MergeKLists();
        // [1,4,5],[1,3,4],[2,6]
        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode l3 = new ListNode(2, new ListNode(6));
        
        ListNode[] lists = {l1, l2, l3};
        
        ListNode listNode = m.mergeKLists(lists);
        System.out.println(listNode);
    }
}
